A communication network system is known in which a communication network including a plurality of nodes is centrally managed by a management server. When the management server receives a path setting request for a certain flow, it determines a communication path of the flow on the communication network. Hereinafter, the management server which determines a communication path of a flow as described above will also be referred to as a “control server”.
As an algorithm for acquiring the shortest path from a source node to a destination node, the Dijkstra's Algorithm is described in NPL 1. When a communication of a plurality of flows is to be established between a source node and a destination node, however, simply using the Dijkstra's Algorithm will cause the same communication path (the shortest path) to be set for the plurality of flows. This increases the load on that communication path, leading to a reduction in communication efficiency.
In order to distribute the load, different communication paths may be suitably set for different flows between the same source node and the same destination node. To this end, it is conceivable to extract not only the shortest path but also other communication paths between the source node and the destination node. As the techniques for acquiring a plurality of communication paths from a source node to a destination node, the following techniques are known.
NPL 2 describes a k-shortest path method, according to which k shortest paths are extracted by the Dijkstra's Algorithm to assign a path of a packet or a flow at random to one of the k shortest paths. This method allows a plurality of paths to be acquired from a source node to a destination node.
In the case of using the k-shortest path method, however, the Dijkstra's Algorithm is used to acquire the communication paths, requiring a huge amount of calculation.
NPL 3 describes a method for acquiring a path from a source node to a destination node while distributing the load and reducing the amount of calculation. According to the method described in NPL 3, a node on a path generates a transfer probability table for a certain destination and uses the transfer probability table to transfer a packet on the basis of the probability. In this case, the transfer probability table has, for a destination node, neighboring switches and transfer probabilities thereto. When an address of the destination node is determined, a packet is probabilistically transferred to a neighboring node.
With the method described in NPL 3, a transfer probability table can readily be built, permitting a reduction in amount of calculation.
While the method described in NPL 3 is for probabilistic packet transfer, this method is applicable to flow transfer as well.
As a method for setting different communication paths for different flows between the same source node and the same destination node, a technique called “OpenFlow” is proposed in NPL 4. According to the “OpenFlow” technique, a communication is regarded as an end-to-end flow, and a path control, a recovery, load distribution, and optimization are performed in units of flows. An OpenFlow switch, which functions as a transfer node, is provided with a secure channel for communication with an OpenFlow controller, and operates in accordance with a flow table which is added or rewritten as appropriate in accordance with an instruction from the OpenFlow controller. The flow table defines, for each flow, a combination of a rule to be checked with a packet header, an action defining the process content, and flow statistical information.
For example, when an OpenFlow switch receives a first packet, it searches a flow table for an entry having a rule (FlowKey) that matches the header information of the received packet. When the search finds an entry that matches the received packet, the OpenFlow switch processes the received packet in accordance with the process content described in the action field of the entry. On the other hand, when the search finds no entry that matches the received packet, the OpenFlow switch transfers the received packet to an OpenFlow controller, via a secure channel, to request the controller to determine a path of the packet on the basis of the source and destination of the received packet. The OpenFlow switch then receives from the controller a flow entry that implements the same, and updates the flow table.
In the method in which a transfer probability table is used to transfer a flow in a probabilistic manner, the next hop is selected probabilistically. This may cause a routing loop to occur, leading to a reduction in communication efficiency.
PTL 1 describes, in a method for probabilistically transferring a flow using a transfer probability table, a method for working around a routing loop in the event that the loop occurs.
According to the method described in PTL 1, a node is selected at random from among next hop node candidates, a target node is updated to the selected next hop node, and it is checked whether the target node is a node that has already been passed through. If the target node is the one that has already been passed through, it is determined that a loop has occurred, and the path falls back to the state before the occurrence of the loop. That is, according to this method, every time an occurrence of a loop is detected, selection of the next hop node is performed again.
With the method described in PTL 1, a path may be determined without causing a routing loop. Under a circumstance where routing loops would occur frequently, however, it is highly likely that a target node is a node that has already been passed through and, hence, the fall back of path would likely be repeated a large number of times. As a result, with the method described in PTL 1, the amount of calculation for path computation will be increased, so that the path computation cannot be performed rapidly.